cs / machine-learning
1. QR 分解
Eigenvalues of 以及 是 的 squared singular values
QR 分解和 SVD(奇异值分解,Singular Value Decomposition)是线性代数中两种重要的矩阵分解方法,常用于数据分析、数值计算、信号处理等领域。
1. QR 分解
QR 分解是将一个矩阵分解为一个正交矩阵(Q)和一个上三角矩阵(R)的过程。
定义
如果 AA 是一个 m×nm \times n 的矩阵,且 m≥nm \geq n,那么 QR 分解可以表示为:
A=QR
其中:
- QQ 是一个 m×mm \times m 的正交矩阵,满足 Q⊤Q=IQ^\top Q = I(正交矩阵的列是标准正交基向量)。
- RR 是一个 m×nm \times n 的上三角矩阵。
用途
- 求解线性方程组(如最小二乘问题)。
- 数值算法(如 QR 算法,用于计算特征值)。
- 信号处理和数据降维。
计算方法
- Gram-Schmidt 正交化:对矩阵的列向量进行正交化。
- Householder 反射:构造反射矩阵以逐步将矩阵转换为上三角形式。
- Givens 旋转:使用旋转矩阵消除非对角线元素。
2. SVD 分解
SVD 分解是将一个矩阵分解为三个特殊矩阵的乘积。
定义
如果 AA 是一个 m×nm \times n 的矩阵,那么 SVD 可以表示为:
A=UΣV⊤A = U \Sigma V^\top
其中:
- UU 是一个 m×mm \times m 的正交矩阵,其列是 AA⊤A A^\top 的特征向量。
- Σ\Sigma 是一个 m×nm \times n 的对角矩阵,其对角线上的元素是 AA 的奇异值,按从大到小排序,其余元素为 0。
- VV 是一个 n×nn \times n 的正交矩阵,其列是 A⊤AA^\top A 的特征向量。
用途
- 数据降维(如主成分分析,PCA)。
- 低秩近似(用于图像压缩或推荐系统)。
- 求解病态线性系统。
- 信号处理和特征提取。
计算方法
- 奇异值通过计算 A⊤AA^\top A 和 AA⊤A A^\top 的特征值和特征向量获得。
- 使用数值算法(如 Jacobi 方法或基于 QR 分解的算法)。
比较 QR 和 SVD
| 特性 | QR 分解 | SVD 分解 |
|---|---|---|
| 适用矩阵 | 方阵或任意矩阵 | 任意矩阵 |
| 分解形式 | A=QRA = QR | A=UΣV⊤A = U \Sigma V^\top |
| 矩阵性质 | 正交矩阵和上三角矩阵 | 正交矩阵和对角矩阵 |
| 用途 | 数值计算、求解方程 | 数据降维、特征提取、矩阵近似 |
| 计算复杂度 | 较低(特别是方阵) | 较高(但结果更强大) |
总之,QR 分解偏向于数值线性代数的基本操作,而 SVD 分解具有更广泛的应用,在机器学习、数据处理等领域尤为重要。